package org.geekbang.time.mathbasicthought.lesson3_iteration;

import java.util.Arrays;

public class DictionarySearch {
    public static void main(String[] args) {
        String[] dictionary = {"i", "am", "one", "of", "the", "authors", "in", "geekbang"};

        Arrays.sort(dictionary);

        String wordToFind = "i";

        boolean found = search(dictionary, wordToFind);
        if (found) {
            System.out.println(String.format("找到了单词%s", wordToFind));
        } else {
            System.out.println(String.format("未能找到单词%s", wordToFind));
        }

    }

    /**
     * 二分法查找字典中的某个单词
     *
     * @param dictionary 字典，有序的
     * @param wordToFind 待查找的单词
     * @return 是否找到
     */
    public static boolean search(String[] dictionary, String wordToFind) {
        if (dictionary == null)
            return false;

        if (dictionary.length <= 0)
            return false;

        int left = 0, right = dictionary.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (dictionary[mid].compareTo(wordToFind) == 0)
                return true;
            else {
                if (dictionary[mid].compareTo(wordToFind) < 0)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return false;
    }
}
